package org.ymx.myString;

/**
 * @desc:
 * @author: YanMingXin
 * @create: 2021/8/24-10:03
 **/
public class myString {

    public static void main(String[] args) {
        System.out.println(strcmp1());
    }


    /**
     * 经典字符串模式匹配
     *
     * @return
     */
    public static int strcmp1() {
        final String source = "ABCDEFG";
        final String pattern = "BCD";
        char[] s = source.toCharArray();
        char[] p = pattern.toCharArray();
        int i = 0;
        int j = 0;
        if (source.length() < pattern.length()) {
            //如果主串长度小于模式串，直接返回-1，匹配失败
            return -1;
        } else {
            while (i < source.length() && j < pattern.length()) {
                //如果i,j位置上的字符匹配成功就继续向后匹配
                if (s[i] == p[j]) {
                    ++i;
                    ++j;
                } else {
                    //i回溯到主串上一次开始匹配下一个位置的地方
                    i = i - (j - 1);
                    //j重置，模式串从开始再次进行匹配
                    j = 0;
                }
            }
            if (j == pattern.length()) {
                //匹配成功
                return i - j;
            } else {
                //匹配失败
                return -1;
            }
        }
    }

    /**
     * KMP算法模式匹配
     *
     * @return
     */
    public static int strcmp2() {
        final String source = "ABCDEFG";
        final String pattern = "BCD";
        int i = 0;
        int j = 0;
        char[] s = source.toCharArray();
        char[] p = pattern.toCharArray();
        int[] next = getNext(p);
        while (i < s.length && j < p.length) {
            if (j == -1 || s[i] == p[j]) {
                ++i;
                ++j;
            } else {
                //如果j != -1且当前字符匹配失败，则令i不变，
                //j = next[j],即让pattern模式串右移j - next[j]个单位
                j = next[j];
            }
        }
        if (j == p.length) {
            return i - j;
        } else {
            return -1;
        }
    }

    /**
     * 已知next[j] = k, 利用递归的思想求出next[j+1]的值
     * 1.如果p[j] = p[k]，则next[j+1] = next[k] + 1;
     * 2.如果p[j] != p[k],则令k = next[k],如果此时p[j] == p[k],则next[j+1] = k+1
     * 如果不相等，则继续递归前缀索引，令k=next[k],继续判断，直至k=-1(即k=next[0])或者p[j]=p[k]为止
     */
    private static int[] getNext(char[] p) {
        int[] next = new int[p.length];
        int k = -1;
        int j = 0;
        //这里采用-1做标识
        next[0] = -1;
        while (j < p.length - 1) {
            if (k == -1 || p[j] == p[k]) {
                ++k;
                ++j;
                next[j] = k;
            } else {
                k = next[k];
            }
        }
        return next;
    }

}
